package Algorithm.sort.basic;

import utils.CommonUtils;

import java.util.Arrays;

/**
 * 希尔排序：设置一个初始距离，称为希尔增量（最原始的即设为数组长度的一半），将相同距离的元素分为一组，然后对各个分组进行插入排序，然后将增量减半，重
 *          复上述过程，直到增量为1，即分组只有一组，此时数组已经大致有序了，再进行插入排序，得有序数组。
 *
 * 优化：将各个分组的插入排序混合同时进行，使数组访问更紧凑，故速度更快（局部性原理）。如写法2所示
 *
 * 性能：希尔排序的时间复杂度为O(n1.3)~O(n2)，与数组的规模和增量的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(n2)，
 *      而Hibbard增量的希尔排序的时间复杂度为O(n3/2)。空间复杂度O(1)。不稳定
 *
 * 适用场景：数据规模中等，数据大体有序的场景
 */
public class ShellSort {

    public static void main(String[] args) {
//        int[] A = new int[]{55, 2, 6, 4, 32, 12, 9, 73, 26, 37, 213, 0, 52};
//        shellSort2(A);
//        System.out.println(Arrays.toString(A));
        int[] A = CommonUtils.getRandomNums(1000000, 1000);
        int[] B = Arrays.copyOf(A,A.length);
        int[] C = Arrays.copyOf(A,A.length);
        long time = System.currentTimeMillis();

        InsertSort.insertSort2(A);
        long time1 = System.currentTimeMillis();
        System.out.println("方法一耗时"+(time1-time));

        shellSort(B);
        long time2 = System.currentTimeMillis();
        System.out.println("方法二耗时"+(time2-time1));

        shellSort2(C);
        long time3 = System.currentTimeMillis();
        System.out.println("方法三耗时"+(time3-time2));
    }

    static void shellSort(int[] A) {
        int length = A.length;
        //d为希尔排序的增量
        for (int d = length/2;d >= 1;d = d/2) {
            //对每个分组进行直接插入排序
            for (int i=0;i < d;i++) {
                for(int j=i+d;j < length;j=j+d) {
                    int temp = A[j];
                    while (j-d>=0 && A[j-d] > temp) {
                        A[j] = A[j-d];
                        j = j-d;
                    }
                    A[j] = temp;
                }
            }
        }
    }

    static void shellSort2(int[] A) {
        int length = A.length;
        //d为希尔排序的增量
        for (int d = length/2;d >= 1;d = d/2) {
            //在每层循环中使第i%d+1个分组的前i/d + 1个元素有序，即每次对一个不同的分组进行一次插排
            for(int i=d;i<length;i++) {
                int temp=A[i];
                int j=i-d;
                while(j>=0 && A[j]>temp)
                {
                    A[j+d]=A[j];
                    j=j-d;
                }
                A[j+d] = temp;
            }
        }
    }
}
/**
 * 简评：为什么希尔能突破O(n2)的界，可以用逆序数来理解，假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数，
 * 可以证明对于随机数组，逆序数是O(n2)的，而如果采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行O(n2)的交换次数，这就是为什么冒泡、插入等算法只能到平方级别的原因，
 * 反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除多个逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了。
 *
 * 最原始的那种增量，即从length逐步减半，其实这还不算最快的希尔，有几个增量在实践中表现更出色，具体可以看weiss的数据结构书，同时里面有希尔排序复杂度的证明，但是涉及组合数学和数论，
 * 希尔排序是实现简单但是分析极其困难的一个算法的例子
 * 参考： https://www.zhihu.com/question/24637339/answer/84079774
 */